The lack of adequate “detect and avoid” and “sense and avoid” capabilities has been a significant technological barrier that has limited the progress of the adoption of unmanned aerial systems (UAS) into the National Airspace System (NAS). Because there are no pilots onboard such systems, a UAS cannot comply with the “see and avoid” requirements that underpin operational safety in the NAS. There is currently a lack of a mature UAS technology capable of automatically detecting other aircraft operating in nearby airspace and successfully maneuvering to avoid them.
A rotorcraft, such as a helicopter, may employ different flight paths such as paths 100 illustrated in FIG. 1. In low level flight 110, the rotorcraft flies relatively low to the ground, but flies along a straight path. In contour flight 120, the rotorcraft maintains a relatively constant height above the ground, making adjustments based on terrain contour. In Nap-Of-the-Earth flight 130, the rotorcraft flies very close to the ground, adjusting height to avoid hitting the ground, avoiding obstacles, and potentially using obstacles and terrain folds as cover.
Both civilian and military types of NOE missions may involve flight very close to the ground, requiring avoidance of obstacles such as trees, poles, wires, and buildings. For military missions, using terrain features as masking from enemy sensors may be beneficial. This NOE flight mode maximizes survivability for military missions because most anti-aircraft (AA) weapons require line-of-sight (LOS) contact for some period of time in order to compute a firing solution. For commercial and civilian operations (e.g., medevac, package delivery, firefighting, etc.), it is often necessary to fly NOE in urban or forested areas rich in ground obstacles.
In manned NOE flight, there is little margin for error for the pilot. At an altitude of 6 meters, for example, a helicopter flying at just 40 kilometers per hour can hit the ground in just half a second. The pilot has to navigate to the target while deciding how to avoid obstacles detected at relatively close ranges of less than 1 km. In the presence of ground-based threats, the pilot also has to remain masked from enemy radar by navigating areas protected by terrain folds. For night and/or bad weather operations, the pilot will generally need to wear display goggles or an eyepiece displaying information from external sensors, such as forward-looking infrared (FLIR), etc. These devices have relatively narrow fields of view and inherent time delays on head tracking motions, which may result in motion sickness for rapid head motions. In medevac missions, the pilot will also look for the injured person's location and lower the transport basket or other gear attached to a steel cable, while keeping the cable free of tangles or obstructions. As a consequence, NOE operations impose extremely high workloads on the flight crew, especially the pilot.
Some conventional optimal NOE trajectory planning solutions use a linear combination of flight time and terrain masking as the performance index. The trajectory masking was assumed to be accomplished if an integral proportional to the helicopter altitude above the terrain was minimized Such solutions required the first and second partial derivatives of the terrain, which could be computed using a cubic polynomial parameterization of the digital terrain map (DTM) elevation data. However, for terrain data obtained in-flight from sensor readings, these derivatives would be very noisy and inexact. The Autonomous Helicopter System (AHS) had a three section knowledge-based architecture: vision, planning, and control. Vision provided the local and global scene analysis that is symbolically represented and passed to planning as the initial route planning constraints. Planning generated a task dependent path for the vehicle to traverse, which assures maximum mission system success as well as safety. Control validated the path and either executed the given route or fed back to previous sections in order to resolve conflicts.
The IBM Advanced Flight Path Management System displayed pilot cues for smooth tracking of the desired flight path. It consisted of an onboard route planner that computed the optimum flight path, minimizing exposure, a covert terrain following function based on an advanced low altitude techniques (ADLAT) terrain following algorithm, a guidance function that determined path errors between the present position and desired flight path, and a flight director function that computed pilot commands for aided manual flight. This approach integrated output from FLIR, multimode radar (MMR), a global positioning system (GPS), a high accuracy inertial navigation system (INS), Doppler radar, air data sensors, and an attitude heading reference system (AHRS).
The NOE path planning problem has been divided into “near field” and “far field” problems. Near field is associated with flight in the next several seconds, in the order of tens of seconds at most. Far field refers to a longer time interval. For example, this time interval may be on the order of tens of minutes. The far field solution as embodied in waypoints is determined during mission planning, and is one of the inputs to the NOE calculation. The near field path planning is carried out over a rectangular region divided into cells, and is based on real-time optimization of a performance measure. The NOE planning system of some conventional approaches is divided into far field planning (i.e., generating the global path between waypoints based on terrain, vehicle resources, and threat information using simulated annealing or dynamic programming), mid-field planning (i.e., refining the flight route generated by the far-field planner for a short duration ahead by referring to more detailed terrain information, possible even terrain masking from threats) and near field obstacle avoidance planning (i.e., maneuvering, based on obstacle detection sensor data, around the nominal path generated by the mid-field planner by a two dimensional range map of range as a function of azimuthal look angle).
In NOE mode, the vehicle flies as close to the ground as vegetation and obstacles safely permit, generally following the contours of the terrain, and thus minimizing exposure to potential threats. The terrain through which the vehicle must fly is considered “hostile” in the sense that there are enemy emplacements with LOS-type sensors such as laser and radar, whose positions are not known. Some information on the enemy sensors and weapons characteristics, such as lock-and-launch times, is known a priori. Also, initial information is available concerning some of the locations and movements of these threats, but the threats are expected to move and/or become active or dormant, and the total number of threats is unknown.
Path planning on hostile terrain has been extensively studied for ground and airborne vehicles. Although there are differences between the conventional solutions to this problem, there has essentially been a convergence to two solution methodologies for planning a path between two points on the terrain. One methodology involves the use of digital terrain elevation data (DTED). DTED subdivides the terrain into “terrain cells” by a homogeneous grid in the horizontal plane. Height information is stored and updated by sensor information for each cell. This data is then processed in order to assign some “weight” to each terrain cell, and then some “cost” function is evaluated to find the “cheapest” (i.e., shortest) path by A* or similar graph search algorithms. Alternatively, the DTED database is processed to create a 2-D polygonal obstacle map, and then a graph-like database, or a range map, is generated that can be searched by a heuristic algorithm. The other methodology involves modeling of the terrain by a smoothing function and applying optimal control theory for trajectory planning. This methodology is not practical for in-flight re-planning mainly because the terrain data provided by the sensors is very noisy.
In the DTED approach, the path generation process first generates the footprint of the flight path on the x-y plane, and then generates the vertical flight path along the footprint. This two-stage approach to path generation requires significantly less complex algorithms than other approaches. The horizontal (i.e., lateral) path may be approximated by straight lines that are made as long as possible to eliminate “digitization bias,” which is a product of requiring paths to stay on the grid graph. The lines may be connected by tangent arcs that would correspond to coordinated aircraft turns without sideslip. The vertical plane is defined by the s (along the x-y path footprint) and z (absolute height) coordinates. The vertical path may be approximated by lines and arcs in the s-z plane. Normal acceleration in the vertical dimension can be related to an effective “vertical” turn radius.
The terrain profile may be generated along the horizontal path. Its parallel profile at the nominal flight height becomes the basis for vertical smoothing. Since helicopters have more strict limitations in negative accelerations than in vertical accelerations, the vertical path may be designed to minimize sudden dives (i.e., push-down maneuvers), following the terrain just close enough to avoid this issue. Several conventional algorithms have been proposed to eliminate push-downs. These include the branch-and-prune technique, optimal control, constant acceleration parabolas, and commanded altitude rate for present ground speed.
The dynamic constraints of the helicopter may be stored in the system as maximum acceleration versus distance, deceleration (i.e., flare) versus distance, and slope versus speed curves (e.g., lateral, longitudinal and vertical maximum accelerations, pitch and roll limits, and maximum angular rates). These constraints are specific to the helicopter and are determined by flight testing or estimated by simulation. The parameters also vary with weather conditions and height.
Standard approaches to modeling the terrain for the obstacle avoidance problem, where the plane is subdivided into obstacles or nonobstacles, include subdivision of the plane into small regular “pixels,” hierarchical subdivision (e.g. quadtree), polygonal description of obstacles, description of obstacles by circles, ellipses, or other non-polygonal objects. The standard approaches may also include description of obstacles by splinegons (i.e., closed curved figures), and decomposition of free space into generalized cylinders. Shortest paths according to Euclidean metrics will be “taut string” paths, like threading a string from start to a goal among obstacles and pulling the string “taut.”
The worst-case running time of the shortest path algorithm on a regular grid with n pixels is O(n log n). However, the path is not the shortest according to the Euclidean metric due to “digitization bias” of the 8-connected grid. For maps given in the form of a list of polygonal obstacles, the shortest path can be found by building a visibility graph of the obstacle space or by building a shortest path map. The computational bottleneck is in the construction of the graph, requiring time O(n2) for most graphs and O(n log n) for sparse graphs. The nodes of the visibility graph are the vertices of the obstacles and the edges do not cross the interior of any obstacle. The graph can be searched using A* or Dijkstra's algorithm. The shortest path map is a subdivision of the plane into regions that are loci of all goal points whose shortest paths to start pass through the same sequence of obstacle vertices. A shortest path is found by location of the goal point in its subdivision, done in time O(n log n) and then backtracking an optimal path (i.e., the “continuous Dijkstra” algorithm). In conclusion, the best terrain model for the NOE in-flight path planning problem is a regular grid, since the height information on each “pixel” (i.e., terrain cell) changes according to real-time sensor data. The problem of “digitization bias” is alleviated by path smoothing.
The problem of finding the shortest path for a vehicle constrained on a non-planar surface is the geodesic problem. In this case, the representation of the surface is in three dimensions: (1) polyhedral—given by faces, edges, and vertices with their corresponding adjacency relationships; (2) contour lines—similar to geological terrain maps, given by iso-elevation curves; and (3) elevation array—a two-dimensional array of numbers representing the altitude at each grid point. Digital terrain databases of the form compiled by the Defense Mapping Agency (also called Digital Terrain Maps (DTMs)) fall into this category.
The solution for a map given by elevation array is analogous to the planar case. For the polyhedral representation, however, the general problem is proved to be NP-hard. For convex polyhedra, the shortest path problem can be solved with complexity O(n2 log n) using shortest path maps.
It is assumed that the map of the terrain represents a set of regions in the plane, each having an associated weight or cost c. This weight specifies the “cost per unit distance” of a vehicle traveling in that region. The objective is to find a path from start to goal in the plane that minimizes total cost according to this weighted Euclidean metric. This weighted region problem is a generalization of the obstacle avoidance problem where the weight for “free space” is 1 and for an “obstacle” is +∞. In military applications, there might be regions exposed to threats having an associated LOS where traveling incurs high costs associated with the danger.
There are two basic types of map representations: regular tessellations (e.g., grids of pixels, or quadtrees) and straight line planar subdivisions. The regular grid of pixels representation is frequently used for terrain data. A set of arrays is provided, each array storing information about some particular aspect (ground cover, land usage, hydrography data, man-made features, and traversability indices). DMA data pixels are usually squares 5, 12.5, or 100 meters on a side. If the terrain map is given as a grid of weighted pixels, the previously presented solution for digitized obstacle maps applies. However, this approach has two main problems: (1) fine grids are needed for good feature representation, which requires a large amount of memory; and (2) digitization bias is caused by confining movements to 8 orientations. Grid graphs of multiple resolution and a hierarchical algorithm can be used to alleviate these problems.
A proposed Spatial Database Management System (SDBMS) consisting of a fully integrated, object-oriented and multiple resolution true spatial representation was shown to significantly enhance problem solving efficiency in information fusion, target recognition, situation assessment, autonomous vehicle control, and planning systems. The hybrid representation consists of: (1) pyramidal multiple resolution, object-oriented spatial representation; (2) region quadtrees; and (3) an object-oriented database. In the pyramidal multiple resolution, object-oriented spatial representation, each pyramid cell is an object that includes a concise semantic description of a particular geographic region.
Region quadtrees are regular, recursive decompositions of Euclidean space into equal-sized quadrants, down to a minimum application-dependent resolution. The nodes are object-oriented representations of spatial regions and the arcs define the geographic decomposition. General properties of features are inherited from below. Nearly all quadtree-related algorithms require only integer arithmetic, and many can be implemented using a simple table lookup. In case of terrain without overhangs, linear oct-trees, where a 2n*2n*2n array is subdivided into octants, can be used for storage of three-dimensional objects. The storage overhead for pointers is overcome by encoding the level of subdivision within each node. This method is used to represent non-layered terrain without overhangs. Grid points within a fixed band of elevation can be aggregated to a single block according to their planar position (i.e., a “terrain oct-tree”). There are two major advantages of the use of terrain oct-trees: (1) transformations between terrain coordinates and the address of the corresponding node in the oct-tree are straightforward; and (2) the redundant nodes below the surface can be discarded, significantly reducing the size of the oct-tree. This can be accomplished by projection of the terrain surface.
The object-oriented database includes point features, such as bridges, road intersections, and buildings, within a maximum resolution pyramid cell having a straightforward mapping to the semantic object representation. For the inverse mapping, the semantic object frame points to the appropriate minimum resolution pyramid node(s). Within a maximum resolution pyramid node, each line feature is represented as an object whose attributes are the vertices of a piecewise linear function stored in a quadtree node-offset form. For lines and regions, the relationship between the spatial and object-oriented representations are not 1:1. An explicit pointer links the line segment to the specific semantic object. The inverse link points to the one or more pyramid nodes that contain the line feature. The pyramid provides a hierarchical spatial indexing scheme to generate generic regions, where pyramid nodes up to and including the minimum enclosing quadtree block point directly to the semantic object representation.
The proposed SDBMS may be highly distributed, run by multiple processors, relaxing the execution speed and memory requirements for each individual processor. The regions are simple polygons if the map is modeled as a straight line planar subdivision. This polygonal terrain approach requires significantly less storage capacity than the regular grids. One approach to the solution of the weighted region problem is to subdivide the terrain into regions, place a node at the centroid of each region, connect the nodes of adjacent regions with arcs (weighted by their length) and search this graph for shortest paths. However, this approach produces paths that are far from optimal.
Another approach uses the continuous Dijkstra paradigm and has a complexity of O(n7 L), where L is the number of bits needed to represent the problem data, and ε-optimal paths are computed, which are longer than the optimal paths by ε percent. This approach assumes straight-line planar subdivision, where each region is a closed polygon with an associated weight per unit length travelled in its midst and different weights per unit length travelled on the edges. The shortest paths generated by this approach are piecewise linear, bending only where they pass through a vertex or cross an edge. The bending angle obeys Snell's Law of Refraction, seeking optimality like light travelling through regions with different indexes of refraction. An optimal path can travel along an edge whose cost is less than its neighboring regions.
Consider the special case in which all the weights on faces and edges are either 0 (travel over them can be done at high speeds), 1 (travel can be accomplished at limited speeds only) or +∞ (blocking obstacles). This applies to the maximum concealment problem, where the regions visible to enemy threats have a finite cost, obstacles have infinite cost and other areas are inexpensive. An obstacle avoiding path between two points is desired, which maximizes the concealment and minimizes exposure. Some special cases can be solved with polynomial-time algorithms.
The least risk watchman route problem is a shortest path problem where all the terrain is required to have had LOS contact with the traveling vehicle at some time, while minimizing the exposure to threats. For the case of rectilinear polygons with n sides, there is an algorithm that solves it with complexity O(k2n3) for k threats. The special case of weights {0, 1, +∞} can be solved in polynomial time by shrinking the zero-cost regions to single nodes, building an “extended visibility graph” and searching for the shortest path using Dijkstra or A*.
The special case of navigation on homogeneous terrain with a network of roads is a weighted region problem where all of the regions have the same cost and the edge costs are different. If the shortest paths are assumed to enter a road segment either at one of the endpoints or by hitting at the critical angle of incidence defined by the ratio of the edge's weight to that of the surrounding terrain, then a discrete “critical graph” can be searched for shortest paths. The critical graph's construction and the search can be done in time O(n2), where n is the number of road edges. Generalization to the case of multiple-source points yields Voronoi diagrams. Uniform cost per region can be generalized to a cost function, and the boundaries between regions can be allowed to be curved. A good map representation for realistic vehicle navigation should integrate sensor-based information acquired en-route, and the planner should be able to modify the original planned path according to changing conditions.
Prior approaches to ANOE flight planning are expensive and complex, requiring advanced processing and components. This is not practical for many vehicles. Also, prior approaches cannot produce a guaranteed solution. Accordingly, an improved approach to ANOE path planning may be beneficial.